package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-20 20:56
 **/
public class LeetCode253 {

    //有序化
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;

        //分别维护开始时间和结束时间
        int[] start = new int[n];
        int[] end = new int[n];

        for (int i = 0; i < n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        //对开始时间和结束时间排序
        Arrays.sort(start);
        Arrays.sort(end);

        //需要使用的会议室数量
        int rooms = 0;

        //分别指向开始时间和结束时间数组的当前位置
        int sp = 0;
        int ep = 0;
        while (sp < n) {
            //此时有会议结束了,空出一间会议室,rooms - 1,ep + 1
            if (start[sp] >= end[ep]) {
                rooms -= 1;
                ep += 1;
            }

            //使用一间会议室,romms + 1,sp + 1
            rooms += 1;
            sp += 1;
        }

        return rooms;
    }


    //优先队列
    /*public int minMeetingRooms(int[][] intervals) {
        //按照开始时间进行排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        //构建小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        //将第一场会议的结束时间添加到堆顶
        pq.offer(intervals[0][1]);

        //如果当前会议的开始时间>=堆中最小的会议结束时间,对应元素弹出
        for (int i = 1; i < intervals.length; ++i) {
            if (intervals[i][0] >= pq.peek()) {
                pq.poll();
            }
            pq.offer(intervals[i][1]);
        }
        //pq中元素剩余的元素大小就是需要的会议室数量
        return pq.size();
    }*/

}
